package hot100.logos41To50;

import hot100.datastruct.TreeNode;

/**
 * @author logos
 * date 2025/7/14 17:35
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos49 {

    /**
     * 49. 二叉树的最近公共祖先
     * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if (l != null && r != null) {
                return root;
            }
            if (l == null && r == null) {
                return null;
            }
            return l == null ? r : l;
        }
    }
}
